The current invention relates generally to the field of image processing, and, in particular, to a method of controlling the rate and quality of compressed images.
The advent of the Internet coupled with dramatic improvements in software and printing technologies is causing a migration from local printing presses to the semi-automated high-speed and high-volume shops that can be located virtually anywhere in the world. Printer manufacturers, in order to succeed in this new paradigm, are required to make faster and cheaper printers while maintaining the high levels of image quality required by various applications. Consequently, there is an ever increasing need for image compression, not just for storage considerations, but also for enabling the digital circuitry to keep up with the extremely high data rates dictated by the printing process.
These factors impose a strict requirement on the robustness and speed of the compression technology used in these systems. Many printing applications have a strict requirement on the minimum compressed data rate in order to enable the high-speed printing process while at the same time, they also require very high quality decompressed images. Unfortunately, these two requirements are often in direct conflict with one another. In fact, a key factor in the design of many high-speed printing systems is the development of a compression strategy that reduces the amount of compressed data to or below a desired compressed file size (or equivalently, the desired data rate), while still achieving a minimum (or better) level of quality. The current invention deals with the development of such a compression strategy.
A popular technique for the compression of continuous tone images is the JPEG international compression standard. (Digital compression and coding of continuous-tone still imagesxe2x80x94Part I: Requirements and Guidelines (JPEG), ISO/IEC International Standard 10918-1, ITU-T Rec. T.81, 1993, or W. B. Pennebaker and J. L. Mitchell, JPEG Still Image Data Compression Standard, Van Nostrand Reinhold, New York, 1993). Briefly, when using JPEG compression, the digital image is formatted into 8xc3x978 blocks of pixel values, and a linear decorrelating transformation known as the discrete cosine transform (DCT) is applied to each block to generate 8xc3x978 blocks of DCT coefficients. The DCT coefficients are then normalized and quantized using a frequency-dependent uniform scalar quantizer.
In the JPEG standard, the user can specify a different quantizer step size for each coefficient. This allows the user to control the resulting distortion due to quantization in each coefficient. The quantizer step sizes may be designed based on the relative perceptual importance of the various DCT coefficients or according to other criteria depending on the application. The 64 quantizer step sizes corresponding to the 64 DCT coefficients in each 8xc3x978 block are specified by the elements of an 8xc3x978 user-defined array, called the quantization table or xe2x80x9cQ-tablexe2x80x9d. The Q-table is the main component in the JPEG system for controlling the compressed file size and the resulting decompressed image quality.
Each block of the quantized transform coefficients is ordered into a one-dimensional vector using a pre-defined zig-zag scan that rearranges the quantized coefficients in the order of roughly decreasing energy. This usually results in long runs of zero quantized values that can be efficiently encoded by runlength coding. Each nonzero quantized value and the number of zero values preceding it are encoded as a runlength/amplitude pair using a minimum redundancy coding scheme such as Huffman coding. The binary coded transform coefficients along with an image header containing information such as the Q-table specification, the Huffman table specification, and other image-related data are either stored in a memory device or transmitted over a channel.
As mentioned previously, the ability to trade off image quality for compressed file size in JPEG is accomplished by manipulating the elements of the Q-table. In general, each of the 64 components of the Q-table can be manipulated independently of one another to achieve the desired image quality and file size (or equivalently, the desired compression ratio or bit rate) or image quality. However, in most applications, it is customary to simply scale all of the elements of a basic Q-table with a single constant. For example, multiplying all elements of a given Q-table by a scale factor larger than unity would result in a coarser quantization for each coefficient and hence a lower image quality. But at the same time, a smaller file size is achieved. On the other hand, multiplication by a scale smaller than unity would result in a finer quantization, higher image quality, and a larger file size. This scaling strategy for trading image quality for compressed file size is advocated by many developers of JPEG compression products including the Independent JPEG Group (IJG) whose free software is probably the most widely used tool for JPEG compression. A current version of the software is available at the time of this writing from ftp://ftp.uu.net/graphics/jpeg/. The LJG implementation scales a basic Q-table by using a parameter known as the xe2x80x9cIJG quality settingxe2x80x9d, which converts a value between 1 and 100 to a multiplicative scaling factor.
In many applications, an image needs to be JPEG-compressed to a pre-specified file size. This problem is sometimes referred to as xe2x80x9crate controlxe2x80x9d. In the prior art, JPEG rate control is typically accomplished by compressing the image multiple times until the desired file size is achieved. First, the image is compressed using a basic Q-table, e.g., one that has been designed for that application or the example tables given in the JPEG standard specifications. If the target file size is not achieved, the components of the Q-table are appropriately scaled based on a pre-defined strategy, and the image is compressed again with the scaled Q-table. This process is repeated until the compressed file size is within an acceptable range of the target file size. One strategy that can be used to determine the Q-table scaling at each iteration is described in the prior art by Tzou (IEEE Transactions on Circuits And Systems For Video Technology, Vol 1, No. 2, June 1991, pages 184-196). Although this and other similar strategies often provides rapid convergence (usually 3 or less iterations), they usually require the pre-calculation of an operational rate-distortion (R-D) curve for the class of imagery used in that particular application. This curve is constructed by: (i) compressing many representative images using different scaled versions of a basic Q-table; (ii) averaging the resulting file sizes for each Q-table scale to obtain the so-called xe2x80x9ccontrol pointsxe2x80x9d on the curve; and (iii) using piecewise-polynomials to approximate all points between the control points by interpolation to obtain a plot of the average file size against the scaling parameter.
A major drawback of rate control strategies practiced in the prior art is that the various Q-tables used to compress an image to different file sizes are typically scaled versions of a basic Q-table. Although the prior art teaches techniques for the optimization of the Q-table elements for a specific set of viewing and display conditions (see for example, the technique described by Daly in xe2x80x9cApplication of a noise-adaptive contrast sensitivity function to image data compression,xe2x80x9d Optical Engineering, Volume 19, number 8, pages 979-987, August 1990), it is clearly understood that the scaling of such a Q-table to achieve different file sizes is more of a convenience than an optimal strategy. In fact, at the time of this writing, it is stated at the IJG website
(http://www.faqs.org/faqs/compression-faq/part2/index.html) that xe2x80x9cTuning the quantization tables for best results is something of a black art, and is an active research area. Most existing encoders use simple linear scaling of the example tables given in the JPEG standard, using a single user-specified xe2x80x98qualityxe2x80x99 setting to determine the scaling multiplier. This worksfairly well for midrange qualities (not too far from the sample tables themselves) but is quite nonoptimal at very high or low quality settings.xe2x80x9d
A central aspect of the current invention is in providing a method for generating multiple Q-tables (needed to achieve the gamut of compressed file sizes) based on perceptual considerations that correlate well with perceived quality, as opposed to a simple scaling of a basic Q-table.
The present invention is aimed at providing a flexible rate control strategy that allows a user to tradeoff compressed file size for visual image quality in a perceptually optimum manner.
According to a preferred embodiment of this invention, a plurality of Q-tables, corresponding to different levels of visual quality, are generated and each Q-table is indexed with a quality parameter. An example of a quality parameter is the viewing distance for which the image (which has been compressed and decompressed using the corresponding Q-table) will manifest no perceptual loss if viewed by an observer. This viewing distance is referred to as the threshold viewing distance for the corresponding Q-table.
For each original image to be compressed, either the entire image, or a smaller set of image regions deemed to be representative of the original image, are compressed with the plurality of Q-tables, each of which is indexed by a quality parameter. The resulting set of control points, which denote compressed file size as a function of the quality parameter, are referred to as the rate-distortion (R-D) characteristics of the image and are stored in a lookup table. This lookup table, or alternatively, an interpolated version of that using piecewise-polynomials, is then used to make rate-distortion tradeoffs in the system.
These and other aspects, objects, features and advantages of the present invention will be more clearly understood and appreciated from a review of the following detailed description of the preferred embodiments and appended claims, and by reference to the accompanying drawings.
The present invention offers an advantages over prior art by providing a means of generating a plurality of Q-tables based on a model of the human visual system that result in improved image quality compared to simply scaling a basic Q-table.